package java;

public class Question23 {
    public static void main(String[] args) {
        ListNode[] lists = new ListNode[3];
        ListNode head1 = new ListNode(1);
        head1.next = new ListNode(4);
        head1.next.next = new ListNode(5);
        ListNode head2 = new ListNode(1);
        head2.next = new ListNode(3);
        head2.next.next = new ListNode(4);
        ListNode head3 = new ListNode(2);
        head3.next = new ListNode(6);
        lists[0] = head1;
        lists[1] = head2;
        lists[2] = head3;
        ListNode root = mergeKLists(lists);
        while (root != null){
            System.out.println(root.val);
            root = root.next;
        }

    }
    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length < 1){
            return null;
        }
        ListNode current = new ListNode(Integer.MAX_VALUE);
        ListNode head;
        int indexTemp = -1;
        for (int i = 0; i < lists.length ; i ++){
            if (lists[i] != null && lists[i].val <= current.val){
                current = lists[i];
                indexTemp = i;
            }
        }
        if (current.val != Integer.MAX_VALUE){
            lists[indexTemp] = lists[indexTemp].next;
            head = current;
        }else {
            return null;
        }
        merge(lists,current);
        return head;
    }

    private static void merge(ListNode[] lists, ListNode current) {
        if (isEnd(lists)){
            return;
        }
        int indexTemp = -1;
        int maxInt = Integer.MAX_VALUE;
        for (int i = 0; i < lists.length ; i ++){
            if (lists[i] != null && lists[i].val <= maxInt){
                maxInt = lists[i].val;
                indexTemp = i;
            }
        }
        current.next = lists[indexTemp];
        current = current.next;
        lists[indexTemp] = lists[indexTemp].next;
        merge(lists,current);
    }

    private static boolean isEnd(ListNode[] lists) {
        for (int i = 0;i < lists.length; i++){
            if (lists[i] != null){
                return false;
            }
        }
        return true;
    }
}
